#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ret(n + 1);
        for (int i = 1; i <= n; i++)
        {
            int tmp = i;
            int cnt = 0;
            while (tmp)
            {
                tmp &= (tmp - 1);
                cnt++;
            }
            ret[i] = cnt;
        }
        return ret;
    }
};